/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package gka.a1;
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.AbstractQueue;
import java.util.Arrays;
import java.util.Collection;
import java.util.HashMap;
import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Set;
import java.util.Stack;
import org.jgrapht.*;
import org.jgrapht.graph.*;
/**
 *
 * @author David
 */
public class GKAA1 {

    /**
     * Beispielprog zur Demonstration von JGraphT
     * 
     */
    public static boolean tiefensuche(AbstractBaseGraph<String, DefaultWeightedEdge> abg, String start, String ziel){
        Stack<String> ergStack = new Stack<String>();
        Set<String> markiert = new HashSet<String>();
       //Wenn ziel oder startecke nicht in abg, dann false zurückgeben
        if(!abg.containsVertex(ziel) || !abg.containsVertex(start)){
            return false;
        }
        //Startecke alle Nachfolgerecken finden
        ergStack.add(start);
        markiert.add(start);
        
        while(!ergStack.empty()) {
            String source = ergStack.pop();
            Set<DefaultWeightedEdge> outgoing = abg.edgesOf(source);

             for(DefaultWeightedEdge x : outgoing) {
                 String target;
                 if (abg instanceof DirectedGraph)
                     target = abg.getEdgeTarget(x);
                 else
                     target = abg.getEdgeSource(x).equals(source) ? abg.getEdgeTarget(x) : abg.getEdgeSource(x);
                 
                 if (target.equals(ziel))
                     return true;
                 if (!markiert.contains(target)) {
                     markiert.add(target);
                     ergStack.add(target);
                 }
             }
        }
        return false;
    }
    
    public static boolean breitensuche(AbstractBaseGraph<String, DefaultWeightedEdge> abg, String start, String ziel){
        Queue<String> ergQueue = new PriorityQueue<String>();
        Set<String> markiert = new HashSet<String>();
       //Wenn ziel oder startecke nicht in abg, dann false zurückgeben
        if(!abg.containsVertex(ziel) || !abg.containsVertex(start)){
            return false;
        }
        //Startecke alle Nachfolgerecken finden
        ergQueue.add(start);
        markiert.add(start);
        
        while(!ergQueue.isEmpty()) {
            String source = ergQueue.poll();
            Set<DefaultWeightedEdge> outgoing = abg.edgesOf(source);

             for(DefaultWeightedEdge x : outgoing){
                 String target;
                 if (abg instanceof DirectedGraph)
                     target = abg.getEdgeTarget(x);
                 else
                     target = abg.getEdgeSource(x).equals(source) ? abg.getEdgeTarget(x) : abg.getEdgeSource(x);
                 
                 if (target.equals(ziel))
                     return true;
                 if (!markiert.contains(target)) {
                     markiert.add(target);
                     ergQueue.add(target);
                 }
             }
        }
        return false;
    }
    
    public static void main(String[] args) throws FileNotFoundException, IOException {        
        BufferedReader br = new BufferedReader(new FileReader("C:\\Users\\David\\Documents\\Studium\\Sem III\\Repository\\GKA\\A1\\GKA-A1\\src\\gka\\a1\\Beispielgraph.graph"));//("Z:\\sub\\GKA\\A1\\GKA-A1\\src\\gka\\a1\\Beispielgraph.graph"));
        String str = null;
        String whatgraph = br.readLine();
        AbstractBaseGraph<String, DefaultWeightedEdge> sg;
        
        if(whatgraph.toLowerCase().equals("#ungerichtet"))
            sg = new SimpleWeightedGraph<String, DefaultWeightedEdge>(DefaultWeightedEdge.class);
        else
           sg = new SimpleDirectedWeightedGraph<String, DefaultWeightedEdge>(DefaultWeightedEdge.class);
        
        
        while ((str = br.readLine()) != null) {
                String[] parts = str.split(",");
                sg.addVertex(parts[0]);
                sg.addVertex(parts[1]);
                DefaultWeightedEdge edge = sg.addEdge(parts[0], parts[1]);
                sg.setEdgeWeight(edge, Double.parseDouble(parts[2]));
        }
        System.out.println(sg.toString());
        System.out.println("------------------------------------------------");
        System.out.println(GKAA1.tiefensuche(sg, "Hamburg", "Bremen"));
        System.out.println(GKAA1.tiefensuche(sg, "Magdeburg", "Dresden"));
        System.out.println(GKAA1.tiefensuche(sg, "Karlsruhe", "Bonn"));
        System.out.println(GKAA1.tiefensuche(sg, "Hamburg", "Hannover")); //Bei directed als einziges True
        System.out.println(GKAA1.tiefensuche(sg, "Lübeck", "Kiel"));
        System.out.println(GKAA1.tiefensuche(sg, "Hamburg", "Münster"));
        System.out.println(GKAA1.tiefensuche(sg, "Nürnberg", "Kaiserslautern"));
        System.out.println(GKAA1.tiefensuche(sg, "Leipzig", "Münster"));
        System.out.println(sg.toString());
        System.out.println("------------------------------------------------");
        System.out.println(GKAA1.breitensuche(sg, "Hamburg", "Bremen"));
        System.out.println(GKAA1.breitensuche(sg, "Magdeburg", "Dresden"));
        System.out.println(GKAA1.breitensuche(sg, "Karlsruhe", "Bonn"));
        System.out.println(GKAA1.tiefensuche(sg, "Hamburg", "Hannover")); //Bei directed als einziges True
        System.out.println(GKAA1.breitensuche(sg, "Lübeck", "Kiel"));
        System.out.println(GKAA1.breitensuche(sg, "Hamburg", "Münster"));
        System.out.println(GKAA1.breitensuche(sg, "Nürnberg", "Kaiserslautern"));
        System.out.println(GKAA1.breitensuche(sg, "Leipzig", "Münster"));
        
    }
}
